package com.mgq.algorithm.dp;

/**
 * 给定一个元素为非负整数的二维数组matrix,每行和每列都是从小到大有序的。
 * 再给定一个非负整数aim，请判断aim是否在matrix中。
 */
public class MatrixAim {
    /**
     * 思路:因此matrix数组是有序的
     * 例如
     * 2  3  4  5
     * 6  8  9  10
     * 7 11  13 15
     * 9 12  16 18
     *  假设aim是12
     * 定义一个变量,一开始来到 5位置,判断5是否大于12, 5<12,5左边不用看.因为左边都比5小,来到 10
     * 10小于12,继续往下, 15大于12,往左边 13大于12  往左边 11小于12 往下,相等. 直到到边界.
     * @param matrix
     * @return
     */
    public static boolean process(int[][] matrix,int aim,int a,int b) {
        int rowLength = matrix.length;
        while (a < rowLength &&  b >0) {
            if (matrix[a][b] < aim) {
                //往下
                a++;
            } else if (matrix[a][b] > aim) {
                //往左
                b--;
            } else {
                return true;
            }
        }
        return  false;
    }

    public static boolean exits(int[][] matrix, int aim) {
      return   process(matrix, aim, 0, matrix.length - 1);
    }

    public static void main(String[] args) {
        int[][] matrix=new int[][]{{2,3,4,5},{6,8,9,10},{7,11,13,15},{9,12,16,18}};
        System.out.println(exits(matrix, 17));
        System.out.println(exits(matrix, 16));
        System.out.println(exits(matrix, 3));
        System.out.println(exits(matrix, 22));
    }
}
